/*
 * Copyright (c) 2008, Justin Choy
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 * 
 * 1) Redistributions of source code must retain the above copyright notice, 
 * this list of conditions and the following disclaimer.
 * 
 * 2) Redistributions in binary form must reproduce the above copyright notice, 
 * this list of conditions and the following disclaimer in the documentation 
 * and/or other materials provided with the distribution.
 * 
 * 3) Neither the name of the owner nor the names of its contributors may 
 * be used to endorse or promote products derived from this software without 
 * specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
 * POSSIBILITY OF SUCH DAMAGE.
 */
package algorithms;

import data.Array;
import error.OutOfMemoryException;
import error.ProgrammingErrorException;

/**
 * An example of using the Quick sort Algorithm
 * The quicksort algorithm partitions an array into two groups (bigger and 
 * smaller than the pivot value). It then takes the two groups, calculates new
 * pivot values for each group, and does the same thing again until eventuall
 * the entire array is sorted. For example:
 * 4 7 8 6 3 2 9 (pivot 6)
 * 4 2 3 (pivot 3)   6   8 7 9 (pivot 8)
 * 2 3 4   6   7 8 9 (DONE)
 * 
 * The pivot point is calculated using a median of three method. Choose three
 * random numbers in the array and set the pivot to the median of the three.
 * 
 * O(NlogN)
 * 
 * @author jchoy
 */
public class QuickSort {
    public QuickSort() {
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        try {
            QuickSort.QuickSortedArray array 
                = new QuickSort().new QuickSortedArray();
            
            System.out.println( "Filling Array...");
            array.fillWithRandomNumbers(50000);
            
            System.out.println( "Quick Sorting..." );
            
            long startTime = System.currentTimeMillis();
            array.sort();
            long stopTime = System.currentTimeMillis();
            long sortTime = stopTime - startTime;
            
            System.out.println( "It took " + Long.toString(sortTime) + "ms");
            
            System.out.print( "Testing sort...");
            
            if ( array.isOrdered() == true) {
                System.out.println( "PASS!" );
            } else {
                System.out.println( "FAIL!" );
            }
            
        } catch (ProgrammingErrorException e) {
            System.out.println( e.getMessage() );
        } catch (OutOfMemoryException e) {
            System.out.println(e.getMessage());
        }
    }
    
    
    class QuickSortedArray extends Array {
        public QuickSortedArray() {
        }
        
        /**
         * Sorts the array using quick sort.
         * 
         * @throws ProgrammingErrorException 
         */
        public void sort() throws ProgrammingErrorException {
            quickSort( 0, getNumElements() - 1);
        }
        
        /**
         * The recursive quickSort method. We basically partition, the quicksort
         * the two groups seperated by the pivot. Additionally, since we are
         * using a median of three method to find the pivot point, arrays of 
         * size 1 or 2 must be sorted manually.
         * 
         * @param startIndex The start index of the array to sort
         * @param stopIndex The stop index of the array to sort
         * @throws ProgrammingErrorException
         */
        private void quickSort( int startIndex, int stopIndex )
        throws ProgrammingErrorException {
            int size = stopIndex - startIndex + 1;
            
            if ( size <= 1 ) {
                ; /* No Op */
                
            } else if ( size == 2 ) {
                if ( array[startIndex] > array[stopIndex] ) {
                    swapValue( startIndex, stopIndex );
                }
                
            } else {
                int middleIndex = partitionArray( startIndex, stopIndex );
                quickSort( startIndex, middleIndex - 1 );
                quickSort( middleIndex + 1, stopIndex );
            }
        }
        
        /**
         * Calculates the pivot value for an array using the median of three
         * method.
         * 
         * @param startIndex The start index of the array to sort
         * @param stopIndex The stop index of the array to sort
         * @return The value of the pivot point
         * @throws ProgrammingErrorException
         */
        private long findPivotValue( int startIndex, int stopIndex )
        throws ProgrammingErrorException {
            int middleIndex = ( stopIndex + startIndex ) >>> 1;
            
            /* First sort between start and middle */
            if ( array[startIndex] > array[middleIndex] ) {
                swapValue( startIndex, middleIndex );
            }
     
            /* Sort between start and stop*/
            if ( array[startIndex] > array[stopIndex] ) {
                swapValue( startIndex, stopIndex );
            }
            
            /* Sort between middle and stop */
            if ( array[middleIndex] > array[stopIndex] ) {
                swapValue( middleIndex, stopIndex );
            }
            
            /* We are going to put the pivot value just left of the stop point.
             * Just a place holder because we have to insert it in the middle
             * later
             */
            swapValue( middleIndex, stopIndex - 1 );
            
            return array[stopIndex - 1];   
        }

        /**
         * Partitions array into two groups. Bigger and Smaller than the pivot
         * value. We will return the index of the pivot value.
         * 
         * @param startIndex The start index of the array
         * @param stopIndex The stop index of the array
         * @return The index where we put the pivot point
         * @throws ProgrammingErrorException
         */
        private int partitionArray( int startIndex, int stopIndex )
        throws ProgrammingErrorException {
            
            long pivotValue = findPivotValue( startIndex, stopIndex );
            int pivotIndex = --stopIndex; // Store the pivot index
            
            while (true) {
                
                /* Starting from the left,
                 * find the first element that is larger than the pivot value
                 */
                while ( array[++startIndex] < pivotValue ) {
                    ; /* No Op */
                }
                
                /* Starting from the right, find the first element that is 
                 * smaller than or equal to the pivot value
                 */
                while ( array[--stopIndex] > pivotValue ) {
                   ; /* No Op */
                }
                
                if ( startIndex >= stopIndex ) {
                    break;
                } else {
                    swapValue( startIndex, stopIndex );
                }
            }
            
            /* Now swap the startIndex element with the pivot value. Everything
             * left of the startIndex should be smaller or equal to pivotValue,
             * and everything right of startIndex should be bigger or equal to
             * pivotValue.
             */
            swapValue( startIndex, pivotIndex);
            
            /* Return the index of the pivot point */
            return startIndex;
        }
    }
}
